Под термином implicit bias мы будем понимать явление, состоящее в том, что алгоритм обучения среди всех возможных моделей с нулевым эмпирическим риском выбирает определённые. Это явление можно наблюдать уже на очень простом примере. Рассмотрим задачу линейной регрессии с квадратичной функцией потерь. Пусть имеется $m$ обучающих примеров в евклидовом пространстве размерности $N > m$. В этом случае наша задача $\frac{1}{2} \| X w - y \|_2^2 \to \min_w$ недоопределена: семейство решений составляет линейное многообразие в пространстве весов. Предположим, что матрица объекты-признаки $X \in \mathbb{R}^{m \times N}$ имеет полный ранг по строкам: $\text{rk} X = m < N$.

Рассмотрим динамику градиентного спуска с шагом $\eta$ и нулевой инициализацией весов:

$$w_{k+1} = w_k + \eta X^T (y - X w_k), \quad w_0 = 0.$$

Нам будет удобнее вместо дискретного градиентного спуска рассматривать его непрерывный аналог

$$\frac{dw}{dt} = X^T (y - X w), \quad w(t) = 0,$$

переход к которому соответствует стремлению $\eta$ к нулю и выбору параметризации по $t$, для которой $k = [t / \eta]$ (округление берётся в любую сторону).

Рассмотрим сингулярное разложение $X = U \Sigma V^T$, где $U$ и $V$ ортогональны, а $\Sigma$ – прямоугольная диагональная матрица. Тогда

$$X^T X = V \Sigma^T \Sigma V^T \in \mathbb{R}^{N \times N}$$

и $\text{rk}(X^T X) = m$.

Обозначая $\tilde w = V^T w$ и $\tilde y = V^T X^T y = \Sigma^T U^T y$, получаем:

$$\frac{d\tilde w}{dt} = \tilde y - \Sigma^T \Sigma \tilde w, \quad \tilde w(0) = 0.$$

В координатном виде имеем следующее:

$$\frac{d\tilde w_i}{dt} = \tilde y_i - \sigma_i^2 \tilde w_i, \quad \tilde w_i(0) = 0 \qquad \forall i \in [1:m]$$

и

$$\frac{d\tilde w_i}{dt} = 0, \quad \tilde w_i(0) = 0 \qquad \forall i \in [m+1:N]$$

так как $\Sigma^T \Sigma$ – диагональная матрица, у которой лишь первые $m$ элементов на диагонали не равны нулю, и у вектора $\tilde y = \Sigma^T U^T y$ тоже лишь первые $m$ координат ненулевые.

Так как все $\sigma_i$ для $i=1,\ldots,m$ ненулевые, при $t \to \infty$ получаем следующее решение:

$$\tilde w_i(\infty) = \frac{\tilde y_i}{\sigma_i^2} \quad \forall i \in\{1,\ldots,m\}, \qquad \tilde w_i(\infty) = 0 \quad \forall i \in \{m+1,\ldots,N\}.$$

Это можно записать в эквивалентном матричном виде: $\tilde w(\infty) = (\Sigma^T \Sigma)^+ \tilde y = \Sigma^+ U^T y$, где «+» обозначает взятие псевдообратной матрицы.

Значит, $w(\infty) = V \Sigma^{+} U^T y = X^{+} y = X^T (X X^T)^{-1} y$ в силу того, что матрица $X$ имеет полный ранг по строкам.

Покажем теперь, что это частное решение, найденное градиентным спуском с нулевой инициализацией, имеет наименьшую евклидову норму среди всех минимумов функции потерь $\frac{1}{2} \vert\vert X w - y \vert\vert_2^2$.

Рассмотрим соответствующую функцию Лагранжа:

$$L(w; \lambda) = \frac{\| w \|_2^2}{2} + \lambda^T (y - X w).$$

Здесь $\lambda \in \mathbb{R}^{m}$. Покажем, что пара $(w(\infty), \lambda^* = (X X^T)^{-1} y)$ является критической точкой этой функции:

$$\nabla_\lambda L(w(\infty); \lambda^*) = y - X w(\infty) = y - X X^T (X X^T)^{-1} y = 0;$$

$$\nabla_w L(w(\infty); \lambda^*) = w(\infty) - X^T \lambda^* = X^T((X X^T)^{-1} y - (X X^T)^{-1} y) = 0.$$

В силу выпуклости функции Лагранжа эта критическая точка является точкой глобального минимума.

Случай линейных сетей

Каков implicit bias нейронных сетей? Сходится ли градиентный спуск в решение наименьшей нормы и если да, то о какой норме идёт речь? Частичный ответ на этот вопрос удаётся получить для линейных сетей.

Следуя работе Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, рассмотрим линейную сеть с одним скрытым слоем:

$$f(x; W_{1:2}) = W_2 W_1 x,$$

где $W_1$ и $W_2$ – матрицы $n\times n$.

Поставим задачу многомерной (метка $y$ – вектор) регрессии с квадратичной функцией потерь:

$$\mathcal{L}(W_{1:2}) = \mathbb{E}_{x,y} \vert\vert y - f(x; W_{1:2}) \vert\vert_2^2 \to \min_W$$

Шаг градиентного спуска выглядит следующим образом:

$$\dot{W_1\vphantom{W^T}} = \eta \mathbb{E}_{x,y} W_2^T (y x^T - W_2 W_1 x x^T), \quad \dot{W_2\vphantom{W^T}} = \eta \mathbb{E}_{x,y} (y x^T - W_2 W_1 x x^T) W_1^T,$$

где точка над $W_i$ означает производную по времени (то есть по $t$).

Это нелинейная система матричных дифференциальных уравнений второго порядка; чтобы проинтегрировать её аналитически, нам придётся сделать ряд предположений.

Определим ковариационную матрицу входов $\Sigma_{xx} = \mathbb{E} x x^T$ и матрицу ковариации меток со входами $\Sigma_{xy} = \mathbb{E} y x^T$. Предположим, что данные декоррелированы: $\Sigma_{xx} = I$; этого можно добиться, заменив входы $x$ на $\Sigma_{xx}^{-1} x$. Что касается матрицы ковариации меток со входами, рассмотрим её сингулярное разложение:

$$\Sigma_{xy} = U_2 S_{2,0} V_0^T = \sum_{r=1}^{n} s_r u_r v_r^T.$$

Назовём $s_r$ силой моды с индексом $r$ ковариации между метками и входами.

Сделаем замену координат:

$$\overline{W_2} = U_2^T W_2, \quad \overline{W_1} = W_1 V_0.$$

В новых координатах градиентный спуск принимает вид:

$$\dot{\overline{W}}_1 = \eta \overline{W_2}^T (S_{2,0} - \overline{W_2} \overline{W_1}), \quad \dot{\overline{W}}_2 = \eta (S_{2,0} - \overline{W_2} \overline{W_1}) \overline{W_1}^T.$$

Пусть $\overline{W_1} = [a_1, \ldots, a_n]$ и $\overline{W_2} = [b_1, \ldots, b_n]^T$. Тогда в терминах векторов $a$ и $b$

$$\frac{1}{\eta} \dot a_{\alpha} = s_\alpha b_{\alpha} - \sum_{\gamma=1}^n b_\gamma (b_\gamma^T a_\alpha) = (s_\alpha - (b_\alpha^T a_\alpha)) b_{\alpha} - \sum_{\gamma\neq\alpha} (b_\gamma^T a_\alpha) b_\gamma;$$

$$\frac{1}{\eta} \dot b_{\alpha} = s_\alpha a_{\alpha} - \sum_{\gamma=1}^n (a_\gamma^T b_\alpha) a_\gamma = (s_\alpha - (a_\alpha^T b_\alpha)) a_{\alpha} - \sum_{\gamma\neq\alpha} (a_\gamma^T b_\alpha) a_\gamma.$$

Получилась система векторных дифференциальных уравнений порядка $2n$, всё ещё нелинейная. К счастью, при определённом предположении об инициализации эта система распадается на $n$ независимых систем порядка $2$.

Предположим, что существует ортогональная матрица $R = [r_1, \ldots, r_n]$, такая что при всех $\alpha$ имеет место равенство

$a_\alpha(0) = \tilde a(0) r_\alpha$ и $b_\alpha(0) = \tilde b(0) r_\alpha$

для некоторых скалярных величин $\tilde a(0)$ и $\tilde b(0)$.

Нетрудно заметить, что в этом случае при всех $\alpha$ и в любой момент времени $t$ имеем $a_\alpha(t) = \tilde a(t) r_\alpha$ и $b_\alpha(t) = \tilde b(t) r_\alpha$ для некоторых скалярных величин $\tilde a(t)$ и $\tilde b(t)$ .

Тогда для различных $\alpha$ выражения выше становятся независимыми друг от друга:

$$\frac{d\tilde a}{dt} = \eta (s - \tilde a \tilde b) \tilde b, \qquad \frac{d\tilde b}{dt} = \eta (s - \tilde a \tilde b) \tilde a.$$

Теперь это система нелинейных дифференциальных уравнений второго порядка.

Если $\tilde a = \tilde b$ в начальный момент, то это верно и в любой момент времени. Тогда система выше превращается в одно уравнение первого порядка.

В самом деле, обозначив $u = \tilde a \tilde b$, получаем:

$$\dot u = 2\eta (s - u) u.\quad(1)$$

Это уравнение задаёт следующую динамику градиентного спуска для функции потерь $E(u) = \frac{1}{2} (s - u)^2$ (её глобальный минимум – это $u = s$).

Перед тем, как интегрировать уравнение (1), напомним, как из $u$ перейти обратно к исходным $W_1$ и $W_2$. Имеем для $W_1$:

$$W_1 = \bar W_1 V_0^T, \qquad \bar W_1 = [\tilde a r_1, \ldots, \tilde a r_n], \qquad \tilde a = \sqrt{u}.$$

Аналогично для $W_2$:

$$W_2 = U_2 \bar W_2, \qquad \bar W_2 = [\tilde b r_1, \ldots, \tilde b r_n]^T, \qquad \tilde b = \sqrt{u}.$$

Теперь проинтегрируем уравнение (1) в предположении, что $u(0) = u_0$ и $u(t) = u_f$ для выбранного $t$:

$$t = \frac{1}{\eta} \int_{u_0}^{u_f} \frac{du}{2u (s - u)} \, du = \frac{1}{2 s \eta} \int_{u_0}^{u_f} \left(\frac{du}{u} + \frac{du}{s-u}\right) \, du =$$

$$= \frac{1}{2 s \eta} \left(\ln\left(\frac{u_f}{u_0}\right) - \ln\left(\frac{u_f-s}{u_0-s}\right)\right) = \frac{1}{2 s \eta} \ln\left(\frac{u_f (u_0-s)}{u_0 (u_f-s)}\right).$$

Рассмотрим время, необходимое, чтобы выучить фиксированную долю силы данной моды $u_f = \xi s$, где $\xi \in (0,1)$, стартуя из точки из окрестности нуля $u_0 = \epsilon$. Оно равняется

$$t^{(\xi)} = \frac{1}{2 s \eta} \ln\left(\frac{\xi}{1-\xi} \frac{s-\epsilon}{\epsilon}\right) = \frac{1}{2 s \eta} (\ln(s/\epsilon - 1) - \ln(\xi^{-1} - 1)).$$

Видим, что чем сильнее мода (то есть чем больше $s$), тем быстрее она сходится.

Рассмотрим две моды с силами $s_1$ и $s_2$, такие что $s_1 > s_2$. Насколько вторая (более слабая) мода выучится к моменту, когда первая уже выучится на долю $\xi$? Из уравнения выше имеем:

$$\frac{u_f (u_0-s)}{u_0 (u_f-s)} = e^{2 s \eta t};$$

$$1 - \frac{s}{u_f} = \left(1 - \frac{s}{u_0}\right) e^{-2 s \eta t}.$$

Подставляя $s = s_2$ и $t = t_1^{(\xi)}$, получаем:

$$1 - \frac{s_2}{u_f} = \left(1 - \frac{s_2}{\epsilon}\right) e^{-2 s_2 \eta t_1^{(\xi)}} = \left(1 - \frac{s_2}{\epsilon}\right) e^{-\frac{s_2}{s_1} (\ln(s/\epsilon - 1) - \ln(\xi^{-1} - 1))} \sim\\\sim -\frac{s_2}{\epsilon} \left(\frac{s_1}{\epsilon}\right)^{-\frac{s_2}{s_1}} \left(\frac{\xi}{1-\xi}\right)^{-\frac{s_2}{s_1}} = -s_2 s_1^{-\frac{s_2}{s_1}} \left(\frac{\xi}{1-\xi}\right)^{-\frac{s_2}{s_1}} \epsilon^{\frac{s_2}{s_1} - 1}.$$

Поскольку $s_2 < s_1$, это выражение стремится к минус бесконечности при $\epsilon \to 0$, из чего следует, что $u_f$ стремится к нулю.

Это означает, что если веса в инициализации лежат в окрестности нуля, то к моменту, когда данная мода выучивается на любую фиксированную долю $\xi \in (0,1)$, более слабые моды не успевают выучиться вообще. Таким образом, в любой момент времени $t$ матрица $W_2(t) W_1(t)$ является наилучшим малоранговым приближением заданного ранга матрицы корреляций $\Sigma_{yx}$, причём чем больше $t$, тем больше ранг. Можно сказать, что градиентный спуск с фиксированным числом шагов «предпочитает» решения малого ранга.

В выводе выше, мы использовали ряд предположений, в частности, что вектора $a_{1:n}$, образующие матрицу $\overline{W_1}$, ортогональны в инициализации. Эмпирически те же выводы оказываются верными и без этого предположения, см. графики в оригинальной работе Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. Можно ли их обосновать строго математически? В работах Towards resolving the implicit bias of gradient descent for matrix factorization и Deep Linear Networks Dynamics доказывается, что самая сильная мода выучивается в первую очередь. Тем не менее, на момент написания этого текста остаётся недоказанным, что все моды выучиваются последовательно от сильных к слабым. К сожалению, implicit bias градиентного спуска для нелинейных сетей пока остаётся почти неизученным.